#include <stdio.h>
#include <string.h>

void merge(int arr[],int l,int m,int r){
  printf("%d %d\n",l,r);
  int temp[r-l];
  memcpy(temp,arr+l,(r-l)*sizeof(int));

  int i=l,j=m,k=0;

  while(i < m && j < r){
    if (arr[i] <= arr[j]){
      temp[k++] = arr[i++];
    }else{
      temp[k++] = arr[j++];
    }
  }
  while(i < m){
    temp[k++] = arr[i++];
  }

  while(j < r){
    temp[k++] = arr[j++];
  }

  memcpy(arr+l,temp,(r-l)*sizeof(int));
}

int n;
void merge_sort(int arr[],int l,int r){
  if( r - l <= 1)
    return;
  int m = (l+r)/2;
  // printf("sort=%d  %d %d\n",l,m,r);
  merge_sort(arr,l,m);
  merge_sort(arr,m,r);
  merge(arr,l,m,r);

  for(int j = 0;j < n;j++){
    printf("%d ",arr[j]);
  }
  printf("\n");
}


int main(){

  scanf("%d",&n);
  int arr[n];

  for(int i = 0;i < n;i++){
    scanf("%d",&arr[i]);
  }

  merge_sort(arr,0,n);

  // for(int j = 0;j < n;j++){
  //   printf("%d ",arr[j]);
  // }
}

